package com.example.leetcode.prcatice;

/**
 * 对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。
 *
 * <p>以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。
 *
 * <p>
 *
 * <p>示例 1：
 *
 * <p>输入："13" 输出："3" 解释：13 的 3 进制是 111。 示例 2：
 *
 * <p>输入："4681" 输出："8" 解释：4681 的 8 进制是 11111。 示例 3：
 *
 * <p>输入："1000000000000000000" 输出："999999999999999999" 解释：1000000000000000000 的 999999999999999999
 * 进制是 11
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/smallest-good-base
 */
public class Test483 {

    /**
     * n = k的0次方加到k的m次方，等比数列求和 n = （1-k的m+1次方）/ 1-k 得到 m < logk （n） 根据二项式定理 （数字公式） 看官方解答得到 k = n开m的根号
     * @param n
     * @return
     */
    public String smallestGoodBase(String n) {
        long N = Long.parseLong(n);
        for (int m =59;m>1;m--){
            long k = (long) Math.pow(N,1.0/m);
            if(k<=1){
                continue;
            }
            long s = 0;
            for (int i =0 ;i<=m;i++){
                s = s * k + 1;    //等比数列求和公式
            }
            if (s == N){
                return String.valueOf(k);
            }
        }
        return String.valueOf(N-1);
    }
}
class Demo483{
  public static void main(String[] args) {
    Test483 t = new Test483();
    System.out.println(t.smallestGoodBase("13"));
  }
}